package medium.滑动窗口;

import java.util.HashMap;
import java.util.Map;

/**
 * 3. 无重复字符的最长字串
 * 创建时间：2024-03-20 09:23
 * 地址：https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/
 */
public class 无重复字符的最长字串_3 {
    public static int lengthOfLongestSubstring(String s) {
        // 滑动窗口
        if (s.length() == 0) {
            return 0;
        }
        // 记录滑动窗口中出现的位置
        Map<Character, Integer> map = new HashMap<>();
        char[] charArray = s.toCharArray();
        int left = 0, max = 0;
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(charArray[i])) {
                // 重点：判断重复出现的字符是否还处于滑动窗口内，
                // 因为可能由于上一次的字符重复，会让未重复的字符跳出滑动窗口内，
                // 如果重复出现的字符还在窗口内，就直接使用map中记录的位置，否则left不变（因为重复的字符已经在窗口外了）
                left = Math.max(left, map.get(charArray[i]) + 1);
            }
            map.put(charArray[i], i);
            max = Math.max(max, i - left + 1);
        }
        return max;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("abba"));
    }
}
